#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<int> partitionLabels(string S)
    {
        vector<int> endIndex(26, 0);
        int pos = 0;
        for (char c : S)
        {
            endIndex[c - 'a'] = pos;
            pos++;
        }
        vector<int> ans;
        int start = 0, end = 0;
        int size = S.size();
        pos = 0;
        while (pos < size)
        {
            end = max(end, endIndex[S[pos] - 'a']);
            if (pos == end)
            {
                ans.push_back(end - start + 1);
                start = pos + 1;
            }
            pos++;
        }
        return ans;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    s.partitionLabels("ababcbacadefegdehijhklij");
    return 0;
}
